import sys, copy, math
from gurobipy import *
import numpy as np
import aurora_network

## A routing algorithm is comprised of two paths, one is path selection and the other is weight of traffic allocation along paths
class PathSelector(object):
	def __init__(self, aurora_network, use_multihop=True):
		nblocks = aurora_network.get_num_blocks()
		self.aurora_network = aurora_network
		self.all_interblock_paths = [None] * nblocks
		for i in range(nblocks):
			self.all_interblock_paths[i] = [None] * nblocks
			for j in range(nblocks):
				if i != j:
					self.all_interblock_paths[i][j] = [ (i,j,), ]
					if use_multihop:
						for k in range(nblocks):
							if k != i and k != j:
								self.all_interblock_paths[i][j].append((i, k, j))
		return
	
	# note that the caller MUST NOT edit the returned paths
	def get_all_paths(self):
		return copy.deepcopy(self.all_interblock_paths)


'''
class RoutingController(object):
	def __init__(self, aurora_network, traffic_history):
		self.aurora_network = aurora_network
		return

	# computes the ideal routing performance
	def compute_routing_ideal(self, traffic_matrix, topology_adj_matrix, capacity_matrix): 
		# optimize performance here
		nblocks = fractional_topology.nblocks
		model = Model("Routing minimize mlu")
		model.setParam( 'OutputFlag', False )
		mlu = model.addVar(lb=0., ub=GRB.INFINITY, obj=1., vtype=GRB.CONTINUOUS, name="mlu")
		routing_path_vars = [None] * nblocks
		link_capacity_constraints = [None] * nblocks

		# stage 1: setup all the optimization variables that are the routing weights
		# stage 1.5 : also adds the traffic flow satisfiability constraints
		for i in range(nblocks):
			routing_path_vars[i] = [None] * nblocks
			link_capacity_constraints[i] = [None] * nblocks
			for j in range(nblocks):
				if i != j:
					link_capacity_constraints[i][j] = LinExpr()
					routing_path_vars[i][j] = [None] * len(all_paths[i][j])
					traffic_flow_satisfiability_constraint = LinExpr()
					for path_id in range(len(all_paths[i][j])):
						# path is a list of nodes in a given path
						path = all_paths[i][j][path_id]
						routing_path_vars[i][j][path_id] = model.addVar(lb=0, ub=GRB.INFINITY, 
																		obj=0., vtype=GRB.CONTINUOUS, 
																		name="w" + str(i) + "_" + str(j) + "p_" + str(path_id))
						traffic_flow_satisfiability_constraint.add(routing_path_vars[i][j][path_id], mult=1.)
					model.addConstr(lhs=traffic_flow_satisfiability_constraint, sense=GRB.EQUAL, rhs=traffic_matrix[i][j])
		# stage 2: program and subsequently add link capacity constraints
		for i in range(nblocks):
			for j in range(nblocks):
				if i != j:
					for path_id in range(len(all_paths[i][j])):
						path = all_paths[i][j][path_id]
						curr_node = i
						for next_node_index in range(1, len(path), 1):
							next_node = path[next_node_index]
							link_capacity_constraints[curr_node][next_node].add(routing_path_vars[i][j][path_id], mult=1.)
							curr_node = next_node
						assert(next_node == j)
		for i in range(nblocks):
			for j in range(nblocks):
				if i != j:
					model.addConstr(lhs=link_capacity_constraints[i][j], sense=GRB.LESS_EQUAL, rhs=mlu * fractional_topology.adj_matrix[i][j] * fractional_topology.link_capacity)

		# stage 3: set the objective
		model.setObjective(mlu, GRB.MINIMIZE)
		try: 
			model.optimize()
			# TODO: read in the stretch factor here
			all_traffic = 0.
			single_hop_traffic = 0.
			double_hop_traffic = 0.
			link_traffic_load = [0] * nblocks
			traffic_along_paths = 0.
			for i in range(nblocks):
				link_traffic_load[i] = [0.] * nblocks 
			for ii in range(nblocks):
				for jj in range(nblocks):
					if ii != jj:
						all_traffic += traffic_matrix[ii][jj]
						for path_id in range(len(all_paths[ii][jj])):
							traffic_along_path = routing_path_vars[ii][jj][path_id].x
							if len(all_paths[ii][jj][path_id]) > 2:
								double_hop_traffic += traffic_along_path
								intermediate_node = all_paths[ii][jj][path_id][1]
								link_traffic_load[ii][intermediate_node] += traffic_along_path
								link_traffic_load[intermediate_node][jj] += traffic_along_path
							else:
								single_hop_traffic += traffic_along_path
								link_traffic_load[ii][jj] += traffic_along_path
			#print "ave hop count is: " + str((single_hop_traffic + 2. * double_hop_traffic)/all_traffic)
			# now compute ALU
			total_links = 0.
			lu_aggregate = 0.
			for i in range(nblocks):
				for j in range(nblocks):
					if i != j:
						total_links += fractional_topology.adj_matrix[i][j]
						if fractional_topology.adj_matrix[i][j] > 0.0001:
							lu_aggregate += (link_traffic_load[i][j] / (fractional_topology.link_capacity))
			alu_val = lu_aggregate / total_links
			mlu_val = mlu.x
			return mlu_val, (single_hop_traffic + 2. * double_hop_traffic)/all_traffic, alu_val
		except GurobiError as e:
			print ("EvaluateRoutingPerformanceMLU: Error code " + str(e. errno ) + ": " + str(e))
			return None, None
		except AttributeError :
			print ("EvaluateRoutingPerformanceMLU: Encountered an attribute error ")
			return None, None

	# computes the routing performance for a topology with a given set of routing weights
	# part of static routing
	def compute_routing_performance(self, traffic_matrix, topology_adj_matrix, capacity_matrix, routing_weights):
		nblocks = len(topology_adj_matrix)
		link_utilization = np.zeros((nblocks, nblocks,))
		hop_counter = 0.
		total_traffic = 0.
		for path in routing_weights:
			src = path[0]
			dst = path[-1]
			curr_node = src
			next_node = path[1]
			weight = routing_weights[path]
			traffic_load = weight * traffic_matrix[src][dst]
			total_traffic += traffic_load
			hop_counter += (len(path) - 1) * traffic_load
			for index in range(1, len(path), 1):
				link_utilization[curr_node][next_node] += traffic_load / (topology_adj_matrix[curr_node][next_node] * capacity_matrix[curr_node][next_node])

		# compute the stretch (hop count)
		ave_hop_count = hop_counter / total_traffic
		link_utilization_distribution = sorted(link_utilization.flatten())
		mlu = link_utilization_distribution[-1]
		lu90 = link_utilization_distribution[int(0.9 * len(link_utilization_distribution))]
		lu50 = link_utilization_distribution[int(0.5 * len(link_utilization_distribution))]
		return (mlu, lu90, lu50, ave_hop_count)
	
'''


